1762D - GCD Queries - CodeForces Solution

#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
#define vi vector<int>
#define vll vector<long long>
#define test() ll t; cin >> t; while(t--)
#define eb emplace_back;
#define pairs pair<int,int>
#define p_q priority_queue
 #define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vector<ll>,greater<ll>>
ll mod  = 1000000007;
using namespace std;
#define f(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
template<typename T1, typename T2>
ostream& operator<<(ostream &ostream, const pair<T1, T2> &p) { return (ostream << p.first << ' '<< p.second); }
template<typename T>
ostream& operator<<(ostream &ostream, const vector<T> &c){ for (auto &k : c) cout << k << ' '; return ostream;}


template<typename T1, typename T2>istream& operator>>(istream &istream, pair<T1, T2> &p) { return (istream >> p.first >> p.second); }
template<typename T>
istream& operator>>(istream &istream, vector<T> &c){  int n1 = c.size();for(int i=0;i<n1;++i)cin>>c[i];return istream;}
// save out unordered_map from hacking  by using custom hash
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);}
};
// seive
// -----------------------------------------------------/
void process_sieve(ll a1,vector<bool>&primes,ll n){    
ll y1 = a1;ll y2 = a1;y1 = y1*y2;
while (y1<n){primes[y1] = false;
y2++;y1 = a1*y2;}return ;}
vector<bool> SEIVE(ll n){
vector<bool>primes(n+1,true);
primes[0] = false;primes[1] = false;
for(int i=2;i*i<=n;++i){if (primes[i]){
process_sieve(i,primes,n);}}
return primes;}
// ---------------------------------------------------------
// ---------------------------------------------------------
// Exponentiation for larger power modulo m
//-----------------------------------
ll power(ll x,ll y,ll m){if (y==0)return 1;
ll ans = power(x,y/2,m);ans = (ans*ans)%m;
if (y%2==1){ans = (ans*x)%m;}return ans%m;}
//----------------------------------
// linear diaphantine equation
// ---------------------------------
// extended euclid algo
class triplet{public:ll x; ll y;ll GCD;};
triplet equation(ll a,ll b){if (b==0){triplet t1;t1 = {1,0,a};return t1;}
triplet ans = equation(b,a%b);triplet ans1;ans1 = {ans.y,ans.x - ans.y*(a/b),ans.GCD};return ans1;}
// -----------------------------------
// modular inverse (m need to be prime)
ll modular_inverse(ll a,ll m){ll a2 = power(a,m-2,m);return a2%m;}
// ------------------------------------
ll gcd__(ll a,ll b){if (b==0)return a;return gcd__(b,a%b);}
 ll __gcd(ll a,ll b){ll m1 = -1;if (a<0)a =m1*a;if (b<0)b = m1*b; return gcd__(max(a,b),min(a,b));}
            // ----------------------
// nCr value
//-------------------
ll nCr(ll n,ll r){if (n<r)return 0;r = max(r,n-r);ll ans = 1;for (int i=r+1;i<=n;++i){ans = ans*(ll)i;ans = (ans)%mod;}
ll ans1 = 1;for(int i=1;i<=n-r;++i){ans1 = ans1*(ll)i;ans1 = ans1%mod;}ans1 = modular_inverse(ans1,mod);return (ans*ans1)%mod;}
// ------------------------------
// min  heap 
template<typename T>class compare{public:bool operator()(T* &s1,T* &s2){return s1->c1 > s2->c1;}
};
// short hand type for sorting out list
// sort(begin(v), end(v), [] (int a, int b) { return a > b; });
// string a = a+x   ---->> takes O(a+x)  time
// string a+=x    ----->> takes O(x)   time;
void solve(int start,int n,int index,int val11){
    queue<int>q1;
    f(i,start,n)q1.push(i);
    q1.push(index);
    while(q1.size()>2){
        int n1 = q1.size();
        int maxi = 0;
        int i1 = q1.front();
        q1.pop();
        queue<int>q2;
        queue<int>val;
        while(q1.size()>0){
            int i2 = q1.front();
            q1.pop();cout.flush();
            if (i1 == i2)continue;
            cout<<"? "<<i1<<" "<<i2<<'\n';cout.flush();
            q2.push(i2);
            int x;cin>>x;
            val.push(x);
            maxi = max(maxi,x);
            
        }
        while(q2.size()>0){
            int in = q2.front();
            q2.pop();
            int val1 = val.front();
            val.pop();
            if (val1 == maxi){
                q1.push(in);
            }
        }
        if (q1.size() == 1){
            q1.push(i1);
        }

    }
    int a1 = q1.front();q1.pop();int a2 = q1.front();
    cout<<"! "<<a1<<" "<<a2<<'\n';cout.flush();
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
test(){
    int n;cin>>n;
    int i1 = 1;
    int i2 = n;
    if (n==2){
        cout<<"! "<<1<<" "<<2<<'\n';cout.flush();
        int a1;cin>>a1;
        continue;
    }
    cout<<"? "<<i1<<" "<<i2<<'\n';cout.flush();
    int x;cin>>x;
    if (x>1){
        solve(1,n,n,x);
    }
    else{
        int i3 = 2;
        while(x == 1){
            if (i1 != i3)
            {
                cout<<"? "<<i1<<" "<<i3<<'\n';cout.flush();
                cin>>x;
            }
            if (x>1){
                solve(i3,n,i1,x);
                break;
            }
            if (i3 != i2){
                cout<<"? "<<i3<<" "<<i2<<'\n';cout.flush();
                cin>>x;
            }
            if (x>1){
                solve(i3,n,i2,x);
                break;
            }
            i3++;
        }
    }
    int a1;cin>>a1;


}





      return 0;


}